//https://leetcode.cn/problems/water-and-jug-problem/?envType=daily-question&envId=2024-01-28


class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (targetCapacity > jug1Capacity + jug2Capacity) {
            return false;
        }
        
        if (targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0) {
            return true;
        }
        
        return false;
    }
    
    vector<int> measureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        vector<int> result;
        if (!canMeasureWater(jug1Capacity, jug2Capacity, targetCapacity)) {
            return result;
        }
        
        int gcdValue = gcd(jug1Capacity, jug2Capacity);
        int x0, y0;
        extGcd(jug1Capacity, jug2Capacity, x0, y0);
        
        int x = x0 * (targetCapacity / gcdValue);
        int y = y0 * (targetCapacity / gcdValue);
        
        if (x > 0 && y > 0) {
            // simultaneously fill jug1 and jug2
            while (x > 0 && y > 0) {
                if (jug1Capacity < jug2Capacity) {
                    result.push_back(jug1Capacity);
                    x--;
                    result.push_back(jug2Capacity);
                    y--;
                } else {
                    result.push_back(jug2Capacity);
                    y--;
                    result.push_back(jug1Capacity);
                    x--;
                }
            }
        } else if (x > 0) {
            // fill jug1
            while (x > 0) {
                result.push_back(jug1Capacity);
                x--;
            }
        } else if (y > 0) {
            // fill jug2
            while (y > 0) {
                result.push_back(jug2Capacity);
                y--;
            }
        }
        
        return result;
    }
    
    void extGcd(int a, int b, int& x, int& y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return;
        }
        
        extGcd(b, a % b, x, y);
        int temp = x;
        x = y;
        y = temp - (a / b) * y;
    }
};